11262. Ожидаемая минимальная степень

Вам даны два положительных целых числа n и x.

Вы хотите выбрать x различных целых чисел, каждое от 1 до n включительно. Выбор будет сделан равномерно случайным образом. То есть каждое из возможных x-элементных подмножеств целых чисел от 1 до n будет выбрано с равной вероятностью.

Пусть S будет наименьшим целым числом среди x выбранных. Вычислите ожидаемое значение 2^S. Другими словами, определите среднее значение 2 в степени S, где среднее значение берется по всем возможным выборам x различных целых чисел.

Вход. Два натуральных числа: n (1 ≤ n ≤ 50) и x (1 ≤ x ≤ n).

Выход. Выведите среднее значение 2 в степени S с 4 десятичными цифрами.

Пример входа 1	Пример выхода 1
4 4	2.000000
Пример входа 2	Пример выхода 2
3 2	2.666667

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Выбрать x различных целых чисел из n можно способами.

Рассмотрим, сколько существует подмножеств из x чисел, минимальным элементом в которых будет число i. В такое множество следует выбрать число i и еще x – 1 число, каждое из которых больше i. Чисел, больших i, имеется n – i. Выбрать из них x – 1 число можно способами. Отметим также, что должно выполняться неравенство i + x – 1 ≤ n, чтобы в подмножестве из x элементов наименьшим было i. Откуда i ≤ n – x + 1.

Для вычисления ожидаемого значения 2^S следует вычислить выражение

При x – 1 > n – i считаем = 0.

Пример

В первом тесте единственная возможная ситуация состоит в том, чтобы выбрать (1, 2, 3, 4). Минимальным является число 1, ожидаемое значение равно 2¹ = 2.

Во втором тесте имеется три равновероятных сценария: выбрать можно или {1, 2} или {1, 3} или {2, 3}. Соответствующие значения S равны 1, 1 и 2 соответственно. Средним значением 2^S будет (2¹ + 2¹ + 2²) / 3 = 8 / 3 = 2.6666666.

Вычислим указанный ответ по формуле:

= = =

Реализация алгоритма

Функция Cnk вычисляет значение . Значения биномиального коэффициента будем заносить в ячейки массива dp.

long long dp[51][51];

long long Cnk(int n, int k)

{

if (n == k) return 1;

if (k == 0) return 1;

if (dp[n][k] != -1) return dp[n][k];

return dp[n][k] = Cnk(n - 1, k - 1) + Cnk(n - 1, k);

}

Основная часть программы.

scanf("%d %d", &n, &x);

memset(dp, -1, sizeof(dp));

Вычисляем ответ: a = .

a = 0;

for (i = 1; i <= n - x + 1; i++) // x - 1 <= n - i

a = a + Cnk(n - i, x - 1) * (1LL << i);

res = 1.0 * a / Cnk(n, x);

Выводим ответ.

printf("%lf\n", res);